package com.wrial.middle;
/*
 * @Author  Wrial
 * @Date Created in 17:38 2020/3/29
 * @Description 二叉树的非递归前序遍历
 */

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class LeetCode_144 {


    Stack<TreeNode> stack = new Stack<>();

    List<Integer> ans = new ArrayList<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) return ans;
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            // 中 左 右 (因为使用到栈，所有应该前右左)
            // 为什么LeetCode上不装箱就是结果错了
            ans.add(root.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);

        }
        return ans;

    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
